package src.dp.bag01;

import java.util.Scanner;

public class no_kama46 {  //01背包，二维dp数组
    /**
     * 1. dp数组下标含义：下标为[0-i]的物品里任意取，放进容量 j 的背包，价值总和最大是 dp[i][j]
     * 2. 递推公式：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i] )
     * 3. 初始化数组：初始化第一行、第一列
     * 4. 遍历顺序：对于二维dp数组，先遍历物品后遍历背包 或 先包后物 都可以，内外层for可颠倒
     */
    public static void main(String[] args) {
        dp1();  //dp二维数组
        dp2();  //dp一维数组

    }

    public static void dp1() {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();  //物品种类
        int bagweight = sc.nextInt();  //背包空间
        int[] weight = new int[m];
        int[] value = new int[m];

        for (int i = 0; i < m; i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            value[i] = sc.nextInt();
        }

        int[][] dp = new int[m][bagweight + 1];
        //初始化第一行
        for (int j = weight[0]; j <= bagweight; j++) {
            dp[0][j] = value[0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= bagweight; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i] );
                }
            }
        }
        System.out.println(dp[m - 1][bagweight]);
    }

    /**
     * 1. dp数组下标含义：容量为 j 的背包，所背的物品价值可以最大为 dp[j]
     * 2. 递推公式：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i] )
     * 3. 初始化数组：初始化为 0 就行
     * 4. 遍历顺序：对于一维dp数组，只能先遍历物品后遍历背包，且遍历背包时要 倒序，因为每次更新dp[j]时依靠它前面的某个值
     *      所以当遍历到它时，它前面的值一定要没动过，所以从右往左倒序遍历背包
     */
    public static void dp2() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  //物品种类
        int bagweight = sc.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        int[] dp = new int[bagweight + 1];

        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            value[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {  //先遍历物品
            for(int j = bagweight; j >= weight[i]; j--) {  //后遍历背包，必须从大到小
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i] );
            }
        }
        System.out.println(dp[bagweight]);

    }

}
